package leetcode_core.leetcode_4;

import org.junit.Test;

import java.util.LinkedList;
import java.util.List;

public class longestCommonSubsequenceBF {
    //求解所有的子序列,其实就是在求子集
    //提前加入空集
    private List<String> track1 = new LinkedList<>();
    private List<String> track2 = new LinkedList<>();
    void backtrack(String s, int i,StringBuilder track,List<String> res){
        res.add(track.toString());
        for(int k = i;k<s.length();k++){
            //做出选择
            track.append(s.charAt(k));
            //递归回溯
            backtrack(s,k+1,track,res);
            //撤销选择
            track.deleteCharAt(track.length()-1);
        }
    }
    public void longestCommonSubsequenceBF(){
        String s="abcde";String t="ace";
        //然后分别进行子集的求解,子集就是它们的子序列
        track1.add("");
        track2.add("");
        //至此就求出了最大子序列
        backtrack(s,0,new StringBuilder(),track1);
        backtrack(t,0,new StringBuilder(),track2);
        int maxVal = 0;
        //然后开始比较其两边的长度
        for (String s1 : track1) {
            System.out.println(s1);
        }
        System.out.println();
        for (String s1 : track2) {
            System.out.println(s1);
        }
        for(int i = 0;i<track1.size();i++){
            for(int j = 0;j<track2.size();j++){
                if(track1.get(i).equals(track2.get(j))){//是公共的
                    maxVal = Math.max(maxVal,track1.get(i).length());
                }
            }
        }
        System.out.println(maxVal);
    }

    @Test
    public void test(){
        longestCommonSubsequenceBF();
    }
}